﻿namespace AdvancedTraining.Lesson49;

/// <summary>
/// LeetCode 489. 机器人房间清洁器
/// 给定一个机器人清洁器，它被放置在一个空的网格房间的左上角。
/// 网格房间中的每个格子要么是空的，要么是障碍物。
/// 清洁器用预先设定的好的四个方向移动，在移动时每次只能移动到相邻的格子。
/// 每个格子只能被清洁一次。
/// </summary>
/// <remarks>
/// 算法思路：
/// 1. 深度优先搜索 (DFS) + 回溯算法
/// 2. 使用HashSet记录已访问的位置，避免重复清洁
/// 3. 四个方向：上(0)、右(1)、下(2)、左(3)
/// 4. 递归探索所有可达位置，完成后回溯到原位置
/// 5. 方向变换规律：(i + d) % 4 确保按顺序尝试四个方向
///
/// 时间复杂度：O(m*n)，其中m和n是房间的行数和列数
/// 空间复杂度：O(m*n)，最坏情况下需要存储所有位置
/// </remarks>
public class RobotRoomCleaner //leetcode_0489
{
    // 四个方向：上(0)、右(1)、下(2)、左(3)
    private static readonly int[][] Ds =
    [
        [-1, 0], // 上
        [0, 1],  // 右
        [1, 0],  // 下
        [0, -1]  // 左
    ];

    /// <summary>
    /// 清洁房间的主方法
    /// </summary>
    /// <param name="robot">机器人接口</param>
    public static void CleanRoom(IRobot robot)
    {
        Clean(robot, 0, 0, 0, new HashSet<string>());
    }

    /// <summary>
    /// 递归清洁方法 - 深度优先搜索
    /// </summary>
    /// <param name="robot">机器人接口</param>
    /// <param name="x">当前x坐标</param>
    /// <param name="y">当前y坐标</param>
    /// <param name="d">当前朝向：0上 1右 2下 3左</param>
    /// <param name="visited">已访问的位置集合</param>
    private static void Clean(IRobot robot, int x, int y, int d, HashSet<string> visited)
    {
        // 清洁当前位置
        robot.Clean();
        visited.Add(x + "_" + y);

        // 尝试四个方向
        for (var i = 0; i < 4; i++)
        {
            // 方向变换规律：
            // d = 0 (上): 0 1 2 3 (上右下左)
            // d = 1 (右): 1 2 3 0 (右下左上)
            // d = 2 (下): 2 3 0 1 (下左上右)
            // d = 3 (左): 3 0 1 2 (左上右下)
            var nd = (i + d) % 4;

            // 计算下一步的位置
            var nx = Ds[nd][0] + x;
            var ny = Ds[nd][1] + y;

            // 如果下一个位置未访问且可以移动，则递归清洁
            if (!visited.Contains(nx + "_" + ny) && robot.Move())
            {
                Clean(robot, nx, ny, nd, visited);
            }

            // 转向下一个方向
            robot.TurnRight();
        }

        // 回溯：返回到之前的位置
        // 转向180度
        robot.TurnRight();
        robot.TurnRight();
        // 移动回之前的位置
        robot.Move();
        // 再转180度，恢复原来的朝向
        robot.TurnRight();
        robot.TurnRight();
    }

    /// <summary>
    /// 运行测试用例
    /// </summary>
    public static void Run()
    {
        Console.WriteLine("=== 机器人房间清洁器测试 ===");

        // 测试用例1：简单的2x2房间，无障碍物
        Console.WriteLine("测试用例1: 2x2房间，无障碍物");
        var test1Room = new bool[,] { { false, false }, { false, false } };
        var test1Robot = new TestRobot(test1Room, 0, 0, 0);
        CleanRoom(test1Robot);
        Console.WriteLine($"清洁格子数: {test1Robot.cleanedCount}, 期望: 4");
        Console.WriteLine(test1Robot.cleanedCount == 4 ? "✓ 通过" : "✗ 失败");
        Console.WriteLine($"访问路径: {string.Join(" -> ", test1Robot.path)}");
        Console.WriteLine();

        // 测试用例2：3x3房间，无障碍物
        Console.WriteLine("测试用例2: 3x3房间，无障碍物");
        var test2Room = new bool[,] { { false, false, false }, { false, false, false }, { false, false, false } };
        var test2Robot = new TestRobot(test2Room, 0, 0, 0);
        CleanRoom(test2Robot);
        Console.WriteLine($"清洁格子数: {test2Robot.cleanedCount}, 期望: 9");
        Console.WriteLine(test2Robot.cleanedCount == 9 ? "✓ 通过" : "✗ 失败");
        Console.WriteLine();

        // 测试用例3：有障碍物的房间
        Console.WriteLine("测试用例3: 有障碍物的房间");
        var test3Room = new bool[,] { { false, true, false }, { false, false, false }, { true, false, false } };
        var test3Robot = new TestRobot(test3Room, 1, 1, 0);
        CleanRoom(test3Robot);
        Console.WriteLine($"清洁格子数: {test3Robot.cleanedCount}, 期望: 7");
        Console.WriteLine(test3Robot.cleanedCount == 7 ? "✓ 通过" : "✗ 失败");
        Console.WriteLine();

        // 测试用例4：单格子房间
        Console.WriteLine("测试用例4: 单格子房间");
        var test4Room = new bool[,] { { false } };
        var test4Robot = new TestRobot(test4Room, 0, 0, 0);
        CleanRoom(test4Robot);
        Console.WriteLine($"清洁格子数: {test4Robot.cleanedCount}, 期望: 1");
        Console.WriteLine(test4Robot.cleanedCount == 1 ? "✓ 通过" : "✗ 失败");
        Console.WriteLine();

        // 测试用例5：复杂的障碍物布局
        Console.WriteLine("测试用例5: 复杂障碍物布局");
        var test5Room = new bool[,]
        {
            { false, false, true, false },
            { true, false, false, false },
            { false, true, false, true },
            { false, false, false, false }
        };
        var test5Robot = new TestRobot(test5Room, 0, 0, 0);
        CleanRoom(test5Robot);
        Console.WriteLine($"清洁格子数: {test5Robot.cleanedCount}, 期望: 12");
        Console.WriteLine(test5Robot.cleanedCount == 12 ? "✓ 通过" : "✗ 失败");
        Console.WriteLine();

        Console.WriteLine("=== 算法说明 ===");
        Console.WriteLine("问题：机器人清洁器需要清洁房间中的所有可达格子");
        Console.WriteLine("算法：深度优先搜索 + 回溯，使用HashSet记录已访问位置");
        Console.WriteLine("方向变换：(i + d) % 4 确保按顺序尝试四个方向");
        Console.WriteLine("回溯策略：探索完成后，转向180度移动回原位置");
        Console.WriteLine("时间复杂度：O(m*n)，空间复杂度：O(m*n)");
    }

    /// <summary>
    /// 测试用的机器人实现类（不要提交到LeetCode）
    /// </summary>
    private class TestRobot : IRobot
    {
        private readonly bool[,] room;
        private int x, y, direction;
        public int cleanedCount { get; private set; }
        public readonly List<string> path = new();

        public TestRobot(bool[,] room, int startX, int startY, int startDirection)
        {
            this.room = room;
            x = startX;
            y = startY;
            direction = startDirection;
        }

        public bool Move()
        {
            var dx = Ds[direction][0];
            var dy = Ds[direction][1];
            var nx = x + dx;
            var ny = y + dy;

            // 检查边界和障碍物
            if (nx >= 0 && nx < room.GetLength(0) && ny >= 0 && ny < room.GetLength(1) && !room[nx, ny])
            {
                x = nx;
                y = ny;
                path.Add($"({x},{y})");
                return true;
            }
            return false;
        }

        public void TurnLeft()
        {
            direction = (direction + 3) % 4; // 左转 = 减1，但避免负数所以加3
        }

        public void TurnRight()
        {
            direction = (direction + 1) % 4; // 右转 = 加1
        }

        public void Clean()
        {
            cleanedCount++;
        }

        public string GetPosition() => $"({x},{y})";
        public string GetDirection() => direction switch { 0 => "上", 1 => "右", 2 => "下", 3 => "左", _ => "未知" };
    }

    /// <summary>
    /// 机器人接口（不要提交到LeetCode）
    /// </summary>
    public interface IRobot
    {
        /// <summary>
        /// 尝试向前移动一个格子
        /// </summary>
        /// <returns>如果成功移动返回true，遇到障碍物或边界返回false</returns>
        bool Move();

        /// <summary>
        /// 向左转90度
        /// </summary>
        void TurnLeft();

        /// <summary>
        /// 向右转90度
        /// </summary>
        void TurnRight();

        /// <summary>
        /// 清洁当前格子
        /// </summary>
        void Clean();
    }
}